package com.echo.code.arithmetic.chapter04;

import java.util.*;

/**
 * Created by baiyap on 2018/7/27
 */
public class QuickSort {

  public static void main(String[] args) {
    List<Integer> list = new LinkedList<>(Arrays.asList(10, 5, 2, 2, 3));
    System.out.println(quickSort(list));
  }

  private static List<Integer> quickSort(List<Integer> list) {
    Objects.requireNonNull(list, "invalid parameter");
    if (list.size() <= 1) {
      return list;
    }

    List<Integer> smaller = new LinkedList<>();
    List<Integer> bigger = new LinkedList<>();
    int pivot = list.get(0);
    for (int i = 1; i < list.size(); i++) {
      if (list.get(i) <= pivot) {
        smaller.add(list.get(i));
      } else {
        bigger.add(list.get(i));
      }
    }

    List<Integer> smallerSorted = quickSort(smaller);
    List<Integer> biggerSorted = quickSort(bigger);
    List<Integer> result = new LinkedList<>(smallerSorted);
    result.add(pivot);
    result.addAll(biggerSorted);
    return result;
  }
}
